package dp_algorithm.nowcoder.medium;


/**
 * @author bruin_du
 * @description 求正数数组的最小不可组成和
 * https://www.nowcoder.com/questionTerminal/296c2c18037843a7b719cf4c9c0144e4
 * @date 2022/5/28 17:27
 **/
public class GetFirstUnFormedNum {
    //动态规划的背包问题
    public int getFirstUnFormedNum(int[] arr) {
        int min = arr[0],max = 0;
        for (int i : arr) {
            min = Math.min(i,min);
            max += i;
        }
        //初始化数组匹配下标
        boolean[] form = new boolean[max + 1];
        //这是是从arr取出的数为自身的判断情况
        form[0] = true;
        int sum = 0;
        //逐个取出arr中的数进行匹配
        for (int i = 0; i < arr.length; i++) {
            //控制边界为sum,因为当前大于sum后面的数不可能由取出的arr的数组成
            sum += arr[i];
            for (int j = sum; j >= arr[i]; j--) {
                //如果之前arr中取出的数已经和当前数相等,直接form[i]
                //还需要看减去当前这个数的值是否可以由前面的数组成
                form[j] = form[j - arr[i]] || form[j];
            }
        }
        for (int i = min; i <= max; i++) {
            if(!form[i]) return i;
        }
        return max + 1;
    }
}
